The embodiment relates to a branch prediction mechanism of a computer.
The branch prediction mechanism of the computer predicts a branch destination in the case of executing a branch instruction next by managing an execution history of the branch instructions on the basis of storage addresses (which will hereinafter be termed instruction addresses) in a memory of the instructions executed in the past.
In this case, the branch prediction mechanism determines a set in a storage device based on a set associative system by using a portion of the instruction address (a branch source address) with which the branch instruction is acquired (which means that the instruction is fetched) from a storage source in the past. Then, the branch prediction mechanism stores a branch destination address in one way within the set by tagging still another portion of the branch source address.
Then, the branch prediction mechanism searches the storage device by using the instruction address at an instruction fetch stage. Then, if the branch destination address is stored in the storage device through the branch instruction that was already executed in the past, the branch prediction mechanism predicts that the instruction having the instruction address is the branch instruction and further predicts that a branch to the branch destination will occur.
Then, the branch prediction mechanism obtains the branch destination address from a way in which a content of the tag within the relevant set is coincident with a portion (that should be stored in the tag) of the instruction address of the now-being-fetched instruction. Thus, the branch prediction mechanism can determine in parallel with the instruction fetch whether the instruction is the branch instruction or not (whether or not the branch destination address is stored by tagging a portion of the instruction address of the branch source).
Moreover, this technique enables a computer to obtain the branch destination address predicted if the instruction is the branch instruction. Accordingly, the computer can, even when performing a pipeline process, prepare the instruction fetch at a next stage from the branch destination predicted beforehand in parallel with the present instruction fetch.
Then, if the branch destination obtained from the now-being-executed instruction is the predicted branch destination, the parallel operations at the respective stages can be conducted without stopping the pipeline process. Whereas if the branch destination obtained from the now-being-executed instruction is not the predicted branch destination, it follows that the instruction fetch from a correct branch destination resumes. If the branch destination is not stored in the storage means in the manner of being associated with the instruction address of the now-being-executed branch instruction (if the branch instruction is executed though the branch prediction is not hit) also, the branch prediction can not be utilized, and it follows that there resumes the instruction fetch from the branch destination address acquired by decoding the post-fetching branch instruction.
On the occasion of registering the branch destination address in this conventional branch prediction mechanism, for example, when the branch source address is stored in the storage device (which is referred to as “the address is hit”), a hit way number is attached together with the branch destination address to the branch instruction. Then, data existing in the way specified by the way number is updated based on a result of executing the branch instruction. Namely, for instance, if the branch prediction is correct and if there is a high possibility of similarly branching to this branch destination next, the branch prediction mechanism keeps the way information and updates management information so that the way information is retained to the longest possible degree.
Further, the address is not hit (the branch is off in prediction), and nevertheless the branch actually occurs with the result that the branch destination should be newly stored in the storage device, in which case the branch prediction mechanism stores the branch destination in the way that is predetermined by the management information and should be newly registered with the branch destination, and updates the management information so that the way information is retained as long as possible.
The present applicant already presented a proposal (refer to Patent document 1 given below) for efficiently conducting the way management (for efficiently selecting which way should be preferentially retained within the set determined from the branch source address). This technique is that each way is provided with items of information such as a 1-bit replace flag and a 1-bit valid flag, wherein the associated replace flag is updated so that a next rewriting process to the way, to which the branch destination address is newly written, is set as late as possible.
Then, if there occurs the branch destination that should be newly stored, the way in which the information should be stored next (the information on the present branch prediction destination is to be discarded) is determined from one set of present replace flags (a pattern of bits corresponding to the number of ways).
The following problem, however, is caused in a computer that fetches a plurality of instructions, e.g., four (4) instructions in one fetch operation. To be specific, there is a case where the 4 instructions contain a plurality of branch instructions, and such a necessity arises as to store each branch instruction in a storage device. This is typically a case in which, for example, the branch instruction appearing first in the 4 instructions is not executed, but the branch instruction appearing second is executed. In such a case, generally, the branch destination of the branch, which actually occurs, is registered in the storage device.
In another circumstance, e.g., in a branch prediction mechanism performing the branch prediction based on a global history (global branch history), however, there is a case of having a necessity for storing the branch destination address with no occurrence of the branch in addition to the branch destination with the actual occurrence of the branch. To give one example, if dual loops are formed by two branch instructions, according to the global history, the branch destination, which is not executed at the present, becomes a target to be stored in the storage means as the branch destination that will be executed in the future. Note that the global history was already proposed by the present applicant.
Similarly, as by a superscalar machine, in the case of simultaneously decoding and executing the plurality of instructions by providing a plurality of pipelines, there is also a possibility that the plurality of branch instructions might be retrieved at the same stage. Namely, a set generated from the instruction addresses of the plurality of branch instructions gets coincident, and such a case exists that a conflict occurs between the ways within the set.
Moreover, not even by the system of fetching the plural instructions, if the branch prediction dose not hit, there is a case in which both of the branch destination predicted from the global history and the actual branch destination should be stored.